/* 快速排序：随机选取中间值作为这个标志
   将剩余元素依次与标志进行比较
   小于它就将它放到左侧数组
   大于则放到右侧数组
   之后再递归将左数组和右数组进行调用
   最后返回
*/
const quickSort = (arr) => {
  // 因为arr每次都会进行删除，所以arr在不断变短
  // 递归的退出条件
  if (arr.length <= 1) {
    return arr
  }
  // 取中间的值，splice返回的是被删除的元素数组
  let pivot = arr.splice(Math.floor(arr.length / 2), 1)[0]
  const left = []
  const right = []
  arr.forEach(item => {
    if (item < pivot) left.push(item)
    else right.push(item)
  })
  return quickSort(left).concat(pivot, quickSort(right))
}
let arr = [3, 5, 6, 8, 2, 4, 7, 9, 1, 10]
console.log(quickSort(arr))